---
title: "k叉树 荷马史诗"
created: 2025-11-28
tags:
  - 算法
---

# k叉树 荷马史诗

## 题目 [荷马史诗](https://www.acwing.com/problem/content/151/)

![[image-300b8252.png]]

## 思路分析

![[image-7aa8a1f5.png]]

![[image-6a4157aa.png]]

## 代码实现

```cpp
#include <algorithm>

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

typedef long long LL;

typedef pair<LL, int> PLI;

const int N = 1e5 + 10;

int n, m;

priority_queue<PLI, vector<PLI>, greater<PLI>> heap;

int main() {

    cin >> n >> m;

    for (int i = 0; i < n; i++) {

        LL w;

        cin >> w;

        heap.push({w, 0});

    }

    while ((n - 1) % (m - 1)) {

        heap.push({0ll, 0});

        n++;

    }

    LL res = 0;

    while (heap.size() > 1) {

        LL sum = 0;

        int depth = 0;

        for (int i = 0; i < m; i++) {

            sum += heap.top().first;

            depth = max(depth, heap.top().second);

            heap.pop();

        }

        res += sum;

        heap.push({sum, depth + 1});

    }

    cout << res << endl;

    cout << heap.top().second << endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[雷达设备|雷达设备]] 🏠 [[00-刷题理模型]] ➡️ [[合并果子|合并果子]]